Flash memory arrays are replacing disk storage devices in many applications due to the more rapid response time to client requests for reading and writing data as well as a capability to perform a much higher number of input/output (I/O) operations per second. However, at present, the hardware cost of the flash memory is greater than that of disk and the flash memory is perceived to have a wear out problem, at least if not properly managed.
Large memory systems may service a plurality of individual using applications, and such applications may be independent of each other, as in virtualized systems. In another aspect, a plurality of applications may access and operate on a common memory area, such as where data has been de-duplicated, and is accessed by a plurality of users.
The terms “garbage collection” and “wear leveling” are used to generically describe housekeeping operations that are performed in flash memory systems. Garbage collection may relate to the processes of reclaiming “dead” memory locations created by the writing or re-writing of data to the flash memory. The old data location, representing a value of stored data that has been changed and stored in a new location, or relocated for other reasons, is out-of-date and represents wasted space which needs to be reclaimed so that an appropriate amount of free memory is maintained to permit continued write operations. Write operations continue to occur whenever the data in the memory is being modified by the user, or where additional data is being stored.
To prevent the memory from being filled (that is, to be in a state where there are no free pages) as a consequence of lost space associated with writing or modifying the data contents of the pages of SLC, MLC or TLC NAND flash in a block are written sequentially, from the lowest page address to highest page address. A memory address of a page may be described by the block number on a chip, sequential page number in the block, the sector number in the block, and may include the location of a byte within a sector, if needed.
SLC, MLC and TLC are the current versions of NAND flash memory in production and refer to the number of bits of data that can be stored in each cell of the physical memory (one, two or three). Future developments may result in a higher number of bits per cell, and have already resulted in products where a number of layers of memory are combined in a single chip. The exact configuration of the memory chip is not relevant to the disclosure herein so long as the rules for writing reading and erasing data are similar to the current technology.
A flash memory system 10, shown in a simplified block diagram in FIG. 1 may comprise an interface to the user system 5 and a processor 15 communicating with a flash memory 20 comprising circuits having blocks of memory, each block comprising a plurality of pages. A random access memory 25, which may be volatile memory, may be used as a working memory or buffer. Where NAND flash circuits are used, a person of skill in the art would understand that the pages of a block would need to be erased prior to writing any page of the block a second time. If a page were to be skipped, it cannot be written to until the block is erased. Erase operations can be performed only on an integral block of pages corresponding to the device physical architecture. This property creates the need for “garbage collection” where valid data in the block is relocated so that a block can be erased to reclaim the space that is no longer valid. In simple flash memory systems, each time a page is written the entire block is erased prior to writing the new data. This is inefficient and causes excessive wear as the lifetime of a flash memory chip is characterized by a maximum number of erase cycles.
Writing of data to a block is in response to a write request and therefore may not be temporally continuous. Also, multiple blocks may be available for writing at any epoch, the selection process for blocks being a matter of system design. See, for example, U.S. application Ser. No. 12/796,836, filed on Jun. 9, 2010, which is commonly owned and is incorporated herein by reference.
In an example, a strategy for garbage collection that is used in modern flash memory storage systems, including SSDs (solid state disks), use an abstraction layer often called a FTL (Flash Translation Layer) that relates the user logical address, or LBA (Logical Block Address) to the physical location in the flash memory where the data is actually stored, the physical block address (PBA). The relationship is often said to be embodied in a L2P table (logical-address to-physical-address). A LBA may refer to data at a page size level, corresponding to a PBA having the same capacity in the physical memory and where a block of physical addresses comprises a plurality of PBAs. A person of skill in the art will recognize when a page of data is being referred to rather than a block of pages of data.
The use of these terms respects previous usage while accommodating physical and functional aspects of the NAND flash memory, or memories having comparable function. The use of the terms sector, page, and block n reflects the current commonly accepted terminology for flash memory circuits, and resulted from the adoption of several terms from rotating disk memory technology. The terms page and sector may be replaced by other terminology that is used when referring to data and the location thereof. This should be clear from the context. A person of skill in the art will understand when other equivalent terms are used.
Thus, the granularity of the L2P table may be on a physical page level, such as 4 KB, or a greater or lesser size, depending on the specific system design. Data placement may be managed through the L2P table and with other tables, or lists, of metadata. Herein we will mention some specific metadata, but this is not meant to be a limitation on the amount or type of metadata associated with the stored data. The use of a L2P table permits each page of data to be placed in a physical storage location based on policy, which may involve, for example, out-of-place writes so that the writing of a single page does not necessitate the erasure of an entire block.
In another aspect, the amount of physical memory usually exceeds the amount of memory made available to the user. One may say that the logical address space is less than the physical address space and such abstraction layers as the FTL manage the relationship between logical and physical addresses. The excess of physical memory space with respect to logical address space is termed “overprovisioning”. The overprovisioned space is used, amongst other things to provide for storage of system metadata or spare blocks in the event of a failure of a block, so that the entire chip does not fail in response to a failure of a page or a block to be usable. Herein, we will be using a portion of the overprovisioned physical space to facilitate garbage collection (GC) and wear leveling (WL). As the memory system operates and the GC and WL functions are performed, the overprovisioned blocks of memory may be routinely selected and used to store data, while erased block are returned to the pool of overprovisioned blocks. The functions of GC and WL may be performed separately or as part of a same process.
In an example, a pool of “free” blocks (comprised of a plurality of pages) may be maintained by the GC (garbage collection) algorithm comprising a number of never used blocks or blocks that have already been reclaimed by the GC algorithm and have been subject to the block erase process. A free block is one to which data can be written so as to sequentially fill the pages of the block, in whole or in part. If the process is interrupted, the resumption of the writing of data would begin with the next highest free page of the block. The pool of free blocks may include physical memory that was originally part of the memory reserved for overprovisioning where other free blocks are now allocated to overprovisioning. This would be considered an aspect of wear leveling where free blocks are selected such that a cumulative erasure count of each block in the entire flash memory is approximately equal. Alternatively the wear leveling may pertain to a specific selected portion of the flash memory.
In contrast to the simple garbage collection approach which rewrites each block where a page of memory is being modified, including erasing the block, a more efficient method known as “out-of-place” writes is used. In this approach, each page to be written is sequentially written to the pages of a block in ascending order, with the FTL maintaining the correspondence between logical and physical addresses. The block had been unused of previously erased so that all of the pages of the block are initially available to be written. The writing process continues until the block is full, and a new block is selected to continue to write data. Where the data to be written is a modification of previously stored data at a specific LBA, the PBA at which the “overwritten” data is stored is marked as being stale (dead, invalid) and the new or modified data written to a previously erased page as described above. Ultimately the stale PBAs need to be reclaimed for future use.
The process of garbage collection (reclamation of space) for a system employing out-of-place writes may include: a) selecting a free block if there is not already a block being written to; b) moving valid data from a page of the block selected to be garbage collected to the next sequential page in the selected free block; c) designating the page where the data previously resided as being invalid; d) updating the L2P table to point to the physical page to which the valid data has been moved; e) continuing to move the valid data of the block being GC to new physical storage locations until all of the pages of the block being garbage collected are invalid; and, f) marking the block as being available for an erase operation.
Selection of the block to be garbage collected may be determined by the particular GC algorithm or policy. In an example, a “greedy” GC policy is one where, when the need for garbage collection is determined, the block with the largest number of invalid pages of the blocks that are included in the pool of occupied blocks available for garbage collection is selected. The need may arise when the number of free blocks in a free block pool drops to a threshold. As the system timing and resources permit, GC is performed and blocks that have been GC are erased and either returned to the free block pool or considered part of the overprovisioning.
In another aspect, FIFO policy may be used, where the block containing the oldest data may be GC. In this case, the block may contain an unknown number of invalid pages and the block may have a large number of invalid pages or a small number of invalid pages. In the former case, the number of write operations to perform the recovery of a small number of pages of memory is inefficient.
The data retention time of a flash memory cell is finite and, depending on the usage characteristics, the number of erase cycles and the operating temperature, the data in a block would need to be verified or refreshed periodically so as to avoid encountering high read error rates or eventual data loss.